<!DOCTYPE html>
<html lang="zh-cn">
<head>
  <meta charset="utf-8" />
  <title>动态规划与贪心算法</title>
  <link rel="stylesheet" href="../../css/note.css"/>
</head>

<body>

<h2>动态规划</h2>

<p>
[算法导论 第 15 章]
动态规划 (dynamic programming, dp) 中的 programming 是指一种表格法, 而不是编程.
</p>

<p class="example">
  <b>分拆数</b>
  求将非负整数 m 拆成 n 个非负整数之和的方法数 (n &ge; 1).
  这等于将 m 拆成不超过 n 个正整数之和的方法数.
  例如, 将 m 个相同苹果放入 n 个相同篮子.
</p>

<div class="playground" value="{ m: 5, n: 5 }">
  <p>说明: 5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1
  = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 5*1, 共 7 种.
  </p>
<script type="text">
module.exports = function breakNumber (str) {
  const { m, n } = Playground.parse(str)
  if (n > m) n = m
  let dp = Playground.ones(m+1, n+1)
  for (let i = 1; i <= m; ++i) {
    for (let j = 2; j <= n; ++j) {
      if (j > i) dp[i][j] = dp[i][i]
      else dp[i][j] = dp[i][j-1] + dp[i-j][j]
    }
  }
  return dp[m][n]
}
</script>
</div>

<div class="solution">
  不妨设和式已经按大小排好序:
  <span class="formula">
    `m = m_1 + m_2 + cdots + m_n`,
    `quad m_1 le m_2 le cdots le m_n`.
  </span>
  若和式中含有 0, 则 `m_1 = 0`, 此时只需将 `m` 拆成 `n-1` 个非负整数之和,
  方法数为 `F_(m, n-1)`; 若和式中不含 0, 此时只需将 `m-n` 拆成 `n`
  个非负整数之和, 然后给每个数加 1 即可, 方法数为 `F_(m-n, n)`:
  <span class="formula">
    `F_(m, n) = {
      1, if m = 0 or n = 1;
      F_(m, m), if n gt m;
      F_(m, n-1) + F_(m-n, n), otherwise
    :}`
  </span>
  时间复杂度为 `O(m n)`.
</div>

<p class="example">
  <b>双蛋问题</b>
  设有 f (floors) 层楼, e (eggs) 个鸡蛋, 从 `1 le k le f` 层将鸡蛋丢下.
  假设存在一个临界楼层 `1 le n le f`, 当 `k lt n` 时鸡蛋不碎,
  当 `k ge n` 时鸡蛋破碎. 现在利用手中的鸡蛋做试验, 寻找临界楼层 `n`.
  在最坏情况下, 所需的试验次数最少是多少?
</p>
<div class="playground" value="{ floors: 24, eggs: 4 }">
<script type="text">
module.exports = function dropEggs (str) {
  const { floors, eggs } = Playground.parse(str)
  let dp = Playground.ones(floors+1, eggs+1)
  for (let i = 1; i <= floors; ++i) dp[i][1] = i
  for (let i = 2; i <= floors; ++i) {
    for (let j = 2; j <= eggs; ++j) {
      let tmp = Infinity
      for (let k = 1; k < i; ++k) {
        // 从第 k 层扔鸡蛋, 碎与不碎未知, 应该取最大
        tmp = Math.min(tmp, Math.max(dp[k-1][j-1], dp[i-k][j]))
      }
      dp[i][j] = 1 + tmp
    }
  }
  return dp[floors][eggs]
}
</script>
</div>

<div class="solution">
  从 k 层丢下鸡蛋, 若鸡蛋破碎, 范围缩小到 [1..k-1], 并且鸡蛋数减 1;
  若鸡蛋不碎, 范围缩小到 [k+1..f], 鸡蛋数不变.
  由于事先不知道鸡蛋是否破碎, 考虑最坏情况, 应取两种情况的最大值.
  最后, 关于 k 求最小值, 再加 1 就得到试验的最少次数.
  <span class="formula">
    `F_(f, e) = {
      f, if e = 1 or f = 1;
      1 + min_k max(F_(k-1, e-1), F_(f-k, e)), otherwise
    :}`
  </span>
</div>

<p class="example">
  <b>最大子数组</b>
  找出非空数组 nums 中具有最大和的非空子数组 [lo, hi].
</p>

<div class="playground" value="[-2, 1, -3, 4, -1, 2, 1, -5, 4]">
  <p>说明: 最大子数组是 [4, -1, 2, 1], 和为 6.</p>
<script type="text">
module.exports = function maxSubarr (str) {
  const nums = Playground.parse(str)
  let f = nums[0], g = f
  let lo = 0, hi = 0
  for (let n = 1; n < nums.length; ++n) {
    let tmp = lo
    if (g < 0) [g, tmp] = [0, n]
    g += nums[n]
    if (f < g) [f, lo, hi] = [g, tmp, n]
  }
  return JSON.stringify(nums.slice(lo, hi+1)) + ', ' + f
}
/* 若只需返回最大和, 循环可简化为:
for (let n = 1; n < arr.length; ++n) {
  g = Math.max(g, 0) + arr[n]
  f = Math.max(f, g)
}
*/
</script>
</div>

<p class="solution">
  用 `f_n` 表示 [0, n] 中最大子数组的元素之和,
  `g_n` 表示 [0, n] 中所有以下标 n 为右边界的子数组的最大和.
  若最大子数组不含下标 n, 则 `f_n = f_(n-1)`,
  否则, `f_n = g_n`.
  <span class="formula">
    `f_n = {
      "nums"[0], if n = 0;
      max(f_(n-1), g_n), otherwise;
    :}`<br/>
    `g_n = {
      "nums"[n], if n = 0 or g_(n-1) lt 0;
      g_(n-1) + "nums"[n], otherwise;
    :}`
  </span>
</p>

<ol class="example">
  <b>背包问题</b> [算法导论 16.2 节]
  有 `n` 件商品, `A_k`, 价值 `v_k`, 重 `w_k`, `k = 0, 1, cdots, n-1`;
  有一个容量为 `W` 的背包, 其中 `v_k`, `w_k`, `W` 均为正整数.
  <li>
    <b>0-1 背包问题</b>
    若每件商品都是不可拆分的 (比如金锭), 要么全部装进背包 (1),
    要么不装 (0), 求背包能装下的商品最大总价值.
    <div class="playground" value="{ W:50, w:[10, 20, 30], v:[60, 100, 120] }">
    <p>说明：装入重 20 和 30 的商品, 价值为 100 + 120 = 220.</p>
<script type="text">
module.exports = function pack01 (str) {
  const { W, w, v} = Playground.parse(str)
  const n = w.length
  let dp = Playground.zeros(n+1, W+1)
  for (let i = 1; i <= n; ++i) {
    for (let j = 1; j <= W; ++j) {
      let tmp = dp[i-1][j]
      if (j < w[n-i]) dp[i][j] = tmp
      else dp[i][j] = Math.max(tmp, v[n-i] + dp[i-1][j-w[n-i]])
    }
  }
  return dp[n][W]
}
</script>
    </div>
  </li>
  <li>
    <b>分数背包问题</b>
    若商品可以任意拆分 (比如金沙), 情况又如何?
  </li>
</ol>

<ol class="solution">
  <li>按下标顺序依次判断商品是否应进入背包.
    假设已判断 `n-k` 件商品, 还有 `k` 件尚待判断, 此时背包剩余容量设为
    `w`. 记这时背包能装下的商品最大价值为 `f_(k,w)`, 考虑下一件商品
    `A_(n-k)`, 若装下它, 价值变为 `v_(n-k) + f_(k-1,w-w_(n-k))`,
    否则价值变为 `f_(k-1,w)`:
    <span class="formula">
      `f_(k, w) = {
        0, if k = 0 or w = 0;
        f_(k-1,w){::}, if w lt w_(n-k);
        max(f_(k-1,w), v_(n-k) + f_(k-1,w-w_(n-k))), otherwise;
      :}`
    </span>
  </li>
</ol>

<p class="example">
  <b>最长递增子序列</b>
</p>

<p class="example">
  <b>最优矩阵相乘次序</b>
</p>

<p class="example">
  <b>最优二叉树</b>
</p>

<h2>贪心算法</h2>

<p>Huffman 编码、最小生成树、最短路径问题都是贪心算法的典型应用。</p>

<script src="../../js/note.js?type=cs"></script>
<script src="../../js/playground.js"></script>
</body>
</html>
